package selectsort;

public class Heap {
    /**
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定的排序
     * @param arr
     */
    public void sort(int[] arr) {
        createHeap(arr);
        int end = arr.length - 1;
        while (end >= 0) {
            swap(arr, end, 0);
            siftDown(arr,0,end);
            end--;
        }

    }

    private void swap(int[] arr, int index, int j) {
        int temp = arr[j];
        arr[j] = arr[index];
        arr[index] = temp;
    }
    private void createHeap(int[] arr) {
        for (int parent = (arr.length-1-1) / 2; parent >= 0 ; parent--) {
            siftDown(arr,parent,arr.length);
        }
    }

    private void siftDown(int[] arr, int parent, int length) {
        int child = 2*parent + 1;
        while (child <length) {
            if (child+1 < length && arr[child] < arr[child+1]){
                child++;
            }
            if (arr[child] > arr[parent]) {
                swap(arr,child,parent);
                parent = child;
                child = 2*parent+1;
            } else {
                break;
            }
        }
    }

    public void sort2(int[] arr) {
        createHeap2(arr);
        int end = arr.length - 1;
        while (end >= 0) {
            swap(arr, 0, end);
            siftDown2(arr, 0, end);
            end--;
        }
    }

    private void siftDown2(int[] arr, int parent, int length) {
        int child = 2*parent + 1;
        while (child < length) {
            if (child + 1 < length && arr[child+1] > arr[child]) {
                child++;
            }
            if (arr[child] > arr[parent]) {
                swap(arr, child, parent);
                parent = child;
                child = 2*parent + 1;
            } else {
                break;
            }
        }
    }

    private void createHeap2(int[] arr) {
        for (int parent = (arr.length -1 -1) / 2; parent >= 0 ; parent--) {
            siftDown2(arr, parent, arr.length);
        }
    }
}
